package leetcode_141_160;

import DataStructure.Node;
import leetcode_121_140.*;
import org.junit.Test;
import utils.ListNode;
import utils.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test8 {
    @Test
    // 环形链表
    public void test141() {
        ListNode listNode1=new ListNode(3);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(0);
        ListNode listNode4=new ListNode(-4);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode2;
        System.out.println(new hasCycle_141().hasCycle2(listNode1));
    }

    @Test
    // 环形链表2
    public void test142() {
        ListNode listNode1=new ListNode(3);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(0);
        ListNode listNode4=new ListNode(-4);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode2;
        System.out.println(new detectCycle_142().detectCycle2(listNode1));
    }

    @Test
    //重排链表
    public void test143() {
        ListNode listNode1=new ListNode(3);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(0);
        ListNode listNode4=new ListNode(-4);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;

        new reorderList_143().reorderList(listNode1);
    }

    @Test
    //二叉树的前序遍历
    public void test144() {
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(2);

        TreeNode treeNode4=new TreeNode(3);
        TreeNode treeNode5=new TreeNode(3);

        TreeNode treeNode6=new TreeNode(4);
        TreeNode treeNode7=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new preorderTraversal_144().preorderTraversal(treeNode1));
    }

    @Test
    //二叉树的后序遍历
    public void test145() {
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(2);

        TreeNode treeNode4=new TreeNode(3);
        TreeNode treeNode5=new TreeNode(3);

        TreeNode treeNode6=new TreeNode(4);
        TreeNode treeNode7=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new postorderTraversal_145().postorderTraversal(treeNode1));
    }


    @Test
    //LRU 缓存
    public void test146() {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 0); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//        lRUCache.put(1, 1); // 缓存是 {1=1}
//        lRUCache.put(2, 1); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4

    }


    @Test
    //对链表进行插入排序
    public void test147() {
        ListNode listNode1=new ListNode(3);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(0);
        ListNode listNode4=new ListNode(1);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;

        new insertionSortList_147().insertionSortList(listNode1);
    }

    @Test
    //排序链表
    public void test148() {
        ListNode listNode1=new ListNode(3);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(0);
        ListNode listNode4=new ListNode(1);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;

        new sortList_148().sortList2(listNode1);
    }

    @Test
    //直线上最多的点数
    public void test149() {
        int [][]points = {{1,1},{2,2},{3,3}};
        System.out.println(new maxPoints_149().maxPoints(points));
    }

    @Test
    //逆波兰表达式求值
    public void test150() {
        String[]tokens = {"4","13","5","/","+"};
        System.out.println(new evalRPN_150().evalRPN2(tokens));
    }

    @Test
    //反转字符串中的单词
    public void test151() {
        String s = "  hello world  ";
        System.out.println(new reverseWords_151().reverseWords(s));
    }

    @Test
    //乘积最大子数组
    public void test152() {
        int []nums = {-2,0};
        System.out.println(new maxProduct_152().maxProduct(nums));
    }

    @Test
    //寻找旋转排序数组中的最小值
    public void test153() {
        int []nums = {3,4,5,1,2};
        System.out.println(new findMin_153().findMin(nums));
    }

    @Test
    //寻找旋转排序数组中的最小值2
    public void test154() {
        int []nums = {2,2,2,0,2,2};
        System.out.println(new findMin_153().findMin3(nums));
    }

    @Test
    //最小栈
    public void test155() {
        MinStack minStack = new MinStack();
//        minStack.push(-2);
//        minStack.push(0);
//        minStack.push(-3);
//        System.out.println(minStack.getMin());   // 返回 -3.
//        minStack.pop();
//        System.out.println(minStack.top( ));    // 返回 0.
//        System.out.println(minStack.getMin());   // 返回 -2.

//        minStack.push(2147483646);
//        minStack.push(2147483646);
//        minStack.push(2147483647);
//        minStack.pop();
//        minStack.pop();
//        minStack.pop();
//        minStack.push(2147483647);
//        System.out.println(minStack.getMin());

        minStack.push(512);
        minStack.push(-1024);
        minStack.push(-1024);
        minStack.push(512);
        minStack.pop();
        minStack.pop();
        minStack.pop();
        System.out.println(minStack.getMin());
    }

    @Test
    //相交链表
    public void test160() {
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);


//        listNode1.next=listNode2;
//        listNode2.next=listNode3;
//        listNode3.next=listNode4;

        ListNode listNode5=new ListNode(1);
//        listNode5.next=listNode3;
        new getIntersectionNode_160().getIntersectionNode(listNode1,listNode1);
    }
}

